고속형 병렬 스트림 암호 및 수열 발생기

홍길동, 이순신, 강감찬

(지도교수 : 이세종)

On a High-Speed Parallel Stream Cipher and Sequence Generator

Jil-Dong Hong, Soon-shin Lee, Gam-Chan Kang

요약

통신망의 급격한 발전과 통신 속도의 향상에 따라 암호 알고리듬의 고속화 필요성이 절실하다. 본 논문에서는 LFSR을 고속화하기 위하여 한 클럭에 [eqn: `m`]번의 이동이 이루어지는 고속형 HS-LFSR을 제안하였고, 이를 기본으로 다수의 키 수열 발생기를 병렬 연결하여 속도를 개선시킨 병렬형 스트림 암호를 제안하였다. 그리고 병렬형 스트림 암호 예로서 [eqn: `m`]-병렬 합산 수열 발생기([eqn: `m`]-parallel SUM-BSG)를 제안하여 [eqn: `m`=`8`]인 병렬 발생기를 세부 설계 예시하였으며, 제안된 발생기는 기존의 비도 수준을 유지하면서 처리 속도를 [eqn: `m`]배 높일 수 있음을 확인하였다.

Keyword: 병렬형 스트림 암호, 합산 수열 발생기, 주기, 선형복잡도, 키 수열

I. 서  론

통신망의 급격한 발전과 통신 속도의 고속화 양상에 따라 암호 알고리듬의 고속화 필요성이 절실하다.

암호 방법은 스트림 암호, 블록 암호 그리고 공개 키 암호로 분류될 수 있으며, 블록 암호의 적용 방법은 ECB (electronic codebook) 모드, CFB (cipher feedback) 모드, CBC (cipher block chaining) 모드 및 OFB (output feedback) 모드가 있다 [1]. ECB 모드는 블록 크기의 입력에 대하여 정해진 비밀키와 함수로부터 블록 출력을 생성하는 블록 암호의 일반적인 적용 방법이고, CFB 모드는 출력 암호문을 입

력에 귀환시킴으로써 통신 동기를 자체적으로 확립하는 적용 방법이다. CBC 모드는 송수신 데이터 인증을 위하여 현재 블록 암호문과 다음번 블록 평문을 XOR(exclusive-or)시킨 후 블록 암호에

입력시켜 새로운 출력을 생성하고, 이 출력을 다시 그 다음 번 입력과 XOR시키는 반복 과정으로 최종 인증 값을 얻는 방법이다. 데이터 위조시 최종 인증 값이 바뀌게 되므로 진위 구별이 가능하다. OFB 모드는 블록 암호를 이용하여 랜덤 수열을 발생시켜 스트림 암호와 유사하게 적용하는 방법이다. 그러나 4가지 모드가 암호통신을 하는 실용화 측면에서 채널 에러(암호문에서)에 대부분 취약하거나 또 다른 문제점을 안고 있기 때문에 어떤 대책이 필요하다. 우선 ECB 모드는 채널 에러 시 그 여파가 블록 크기만큼 확산 (error propagation) 되므로 암호 통신으로 인한 통신 선로의 품질 저하를 유발시킨다. 예를 들면, 128-비트 블록 암호를 10-6 비트 에러율(BER, bit error rate)을 갖는 채널에 적용하여 암호화 통신할 경우 이 채널은 에러 특성이 128배 정도 나빠지므로 10-4 ([eqn: ` APPROX `]128 x 10-6) 채널로 기능이 떨어지게 된다. CFB 모드에서는 한 비트의 채널 에러가 블록 크기의 두 배만큼 확산되며, CBC 모드에서는 에러 발생 비트 이후의 모든 블록이 에러가 된다. 블록 암호의 에러 확산을 줄이기 위하여 도입된 OFB 모드는 입력 귀환 비트 수 (블록 크기 보다 작음) 만큼 확산을 줄일 수 있으며, 최선의 경우 1-비트를 귀환시킴으로서 확산을 근본적으로 방지할 수 있다. 하지만 1-비트 크기의 OFB 모드는 일반 ECB 모드보다도 데이터 처리 속도가 블록 크기 배 감소되기 때문에 오히려 통신망 처리 능력을 떨어뜨린다.

한편, 공개 키 암호는 처리 속도가 느리기 때문에 고속 암호용으로의 적용이 어려우며,  스트림 암호는 채널 에러 확산이 없고 안전성(비도 수준) 요소가 몇 가지 측면에서 수학적으로 보장이 되며 고속 처리가 가능한 장점이 있지만, 이 방법 역시 초고속 통신 서비스에 따른 암호 처리를 원활하게 할 수 있을 지에 대한 의문이 제기된다.

본 논문에서는 암호 시스템의 초고속화와 통신 채널을 통할 때 에러 확산이 없는 통신 암호시스템의 설계라는 두 가지 목적을 설정하여 스트림 암호와 블록 암호의 장점을 혼합시킨 병렬형 스트림 암호를 제안한다. 즉, 스트림 암호의 비도 수준과 에러 확산 방지 기능을 유지하면서 구현 방법을 개선하여 블록 암호의 [eqn: `m`]-비트 병렬 동시 처리 기능을 혼합시켜 고속화시킬 새로운 암호 처리 형태이다. 스트림 암호에서 LFSR은 한 클럭에 1-비트씩 이동되며 이를 개선하기 위하여 한 클럭만에 [eqn: `m`]-비트 이동이 가능한 고속형 HS-LFSR을 제안한다. 그리고 1-비트씩 처리되는 비선형 결합함수의 단점을 보완하여 블록 암호처럼 동시에 여러 비트 처리가 가능하도록 [eqn: `m`]-비트 병렬 비선형 결합함수의 일반형을 제안한다. 그리고 병렬형 스트림 암호의 설계 예로 2비트 형태의 합산 수열 발생기 (ISUM-BSG) 여러 개 ([eqn: `m`])를 병렬로 배치하고, 각 수열 발생기에서 출력 수열의 비도 요소가 비슷한 크기를 갖도록 하는 [eqn: `m`]-병렬 ISUM-BSG를 제안한다. 마지막으로 제안 발생기에 대하여 스트림 암호의 비도 요소와 처리 속도를 동일한 조건으로 적용시켜 그 특성을 분석한다.

II. 병렬형 스트림 암호

1. High-speed LFSR 제안

그림 1. LFSR과 HS-LFSR

Fig. 1  LFSR and HS-LFSR.

고속 스트림 암호 구현을 위한 기본 요소로서 그림 1과 같이 고속형 high-speed LFSR (HS-LFSR)을 제안한다.

......

(중략)

......

IV. 시뮬레이션 및 결과

제안된 ###에 대한 시뮬레이션 결과는 표 1과 같이 나타낼 수 있다.

표1. 시뮬레이션 결과

.......

(중략)

......

IV. 결 론

본 논문에서는 기존의 스트림 암호 방식에서 초고속 처리와 통신 채널을 활용한 통신 암호시스템의 구현에 따른 문제점 분석을 통하여 비도 수준을 현 상태로 유지하면서 구현 방법을 개선하여 고속 처리 실현이 가능한 병렬형 스트림 암호를 제안하였다. 우선 고속처리를 위하여 LFSR을 고속화시킨 HS-LFSR을 제안하였으며, 이 발생기에서는 [eqn: `m`]-비트 동시 출력에도 불구하고 각각의 출력이 이중으로 사용되지 않는 특징을 갖는다. 또한 HS-LFSR을 사용하여 구성되는 병렬형 스트림 암호 ([eqn: `m`]-병렬 키 수열 발생기 일반형)는 기존의 스트림 암호에서 1-비트씩 처리되는 단점을 보완하여 동시에 여러 비트가 처리될 수 있도록 블록 암호 개념을 혼합시켰다.

마지막으로 병렬형 스트림 암호의 설계예로 2비트 형태의 개선된 합산 수열 발생기 여러 개를 병렬 배치시켜 [eqn: `m`]-parallel ISUM-BSG를 제시하였으며, 일반 스트림 암호의 비도 요소와 동일한 조건으로 비교 분석하였다. 분석 결과 [eqn: `m`]-비트 생성을 위한 발생기는 각각 원래의 설계 기준을 적용하기 때문에 기존의 비도 수준을 유지할 수 있으며, 병렬 배치로 인한 하드웨어 복잡도는 다소 증가되지만 처리 속도는 [eqn: `m`]배 개선되었다. 결국 제안된 발생기는 하드웨어의 복잡도가 증가 되지만 게이트 집적도가 큰 문제가 되지 않는 현실을 감안할 때 하드웨어 부담을 크게 늘리지 않고도 데이터 처리 속도를 [eqn: `m`]배 향상시킬 수 있는 발생기로써 다가오는 고속화시대에 적합하다고 할 수 있다.

References:

[1] B. Schneier, Applied Cryptography, 2nd Ed., Jhon Wiley & Sons, Inc., 1996.

[2] R. A. Rueppel, Analysis and Design of Stream Ciphers, Springer-Verlag, 1986.

[3] R. A. Rueppel, "Correlation Immunity  and the Summation Generator," Advan- ces in Cryptology, Proceedings of CRYPTO'85, pp. 260-272, 1985.

[4] W. Meier and O. Staffelbach, "Cor- relation Properties of Combiners with Memory in Stream Ciphers," Journal of Cryptology, Vol.5, pp.67-86, 1992.

[5] T. Siegenthaler, "Correlation-Immu- nity of Nonlonear Combining Functions for Cryptographic Applications," IEEE Trans. on Infor. Theo., Vol.IT-30, No. 5, pp. 776-780, Sep. 1984.

[6] X. G. Zhen and J.L. Massey, "A Spectral Characterization of Correlation -  Immune Combining Functions," IEEE Trans. on Infor. Theo., Vol.34, No. 3, May 1988.

[7].